home *** CD-ROM | disk | FTP | other *** search
/ Just Call Me Internet / Just Call Me Internet.iso / prog / atari / m2 / cat3src / cat / boyermoo.d < prev    next >
Text File  |  1997-10-26  |  4KB  |  64 lines
  1. DEFINITION MODULE BoyerMoore;
  2.  
  3. (*==============================================================*
  4.  * Modul:               Stringsuchen nach Boyer-Moore           *
  5.  * Autor:               Dirk Steins/Johannes G”ttker-Schnetmann *
  6.  * erstellt am:         18.04.1992                              *
  7.  * letzte Žnderung am:  19.04.1992                              *
  8.  * Version:             1.0                                     *
  9.  * Interne Version:     V#0001                                  *
  10.  *==============================================================*
  11.  
  12.  Schnelle Stringsuche nach Boyer-Moore, vgl. N. Wirth: Algorithmen
  13.    und Datenstrukturen mit Modula-2, Teubner 1986, S. 67ff
  14.    
  15.  šbernommen aus GMEKernel von Johannes Leckebusch, Peter Hellinger
  16.  Mit einem herzlichen Dank an diese beiden!
  17.  
  18.  *----------------------------------------------------------------------------
  19.  * Datum    Vers. Autor  Žnderung (Arbeitsbericht)                            
  20.  *----------------------------------------------------------------------------
  21.  *----------------------------------------------------------------------------
  22.  *)
  23.  
  24. TYPE longString = ARRAY[0..MAX(LONGINT)] OF CHAR;
  25. TYPE longPtr    = POINTER TO longString;
  26.  
  27. TYPE tableType  = ARRAY[0C..377C] OF CARDINAL;
  28.     (* Tabelle der Zeichenpositionen im String (von hinten) *)
  29.  
  30. PROCEDURE InitTable(VAR table  : tableType;      (* Tabelle fr Boyer-Moore-Suche *)
  31.                     VAR subStr : ARRAY OF CHAR;  (* Zu suchender String           *)
  32.                         len    : CARDINAL;       (* L„nge dieses Strings          *)
  33.                         gross  : BOOLEAN;        (* grož-klein unterscheiden      *)
  34.                         reverse: BOOLEAN);       (* Rckw„rts suchen              *)
  35. (* len muž gr”žer als 0 sein! *)
  36. (* Wenn gross TRUE ist, wird der String entsprechend gewandelt *)
  37.  
  38. PROCEDURE Pos (start  : LONGINT;         (* Startposition im verwendeten Puffer *)
  39.                str    : longPtr;         (* Zeiger auf den Pufferbereich        *)
  40.                pLen   : LONGINT;         (* L„nge dieses Bereiches              *)
  41.            REF substr : ARRAY OF CHAR;   (* gesuchter String                    *)
  42.                len    : INTEGER;         (* L„nge dieses Strings                *)
  43.                gross  : BOOLEAN;         (* gross-klein unterscheiden?          *)
  44.            REF table  : tableType): LONGINT; (* Mit InitTable angelegte Tabelle *)
  45. (* Da die zu verarbeitenden Speicherbl”cke auch recht grož werden k”nnen sollen :-) *)
  46. (* hier die Deklaration als LONGINT. Man k”nnte die Suche notfalls auch stckeln,   *)
  47. (* dann k”nnte es aber Probleme geben, wenn der zu suchende String gerade auf der   *)
  48. (* Blockgrenze steht. L”sung dazu: Einfach um 32k - Stringl„nge nur vorrcken, das  *)
  49. (* w„re mir aber trotzdem im Moment etwas zuviel Aufwand.                           *)
  50. (* Eigentlich ist die Benutzung von LONGINT auch Verschwendung von 2 GB, falls aber *)
  51. (* jemand mehr als 2 GB im Rechner hat, dann kann er sich ja mal melden und bekommt *)
  52. (* dann eine Sonderversion.. :-)                                                    *)
  53.                    
  54. PROCEDURE BackPos (start  : LONGINT;         (* Startposition im verwendeten Puffer *)
  55.                    str    : longPtr;         (* Zeiger auf den Pufferbereich        *)
  56.                    pLen   : LONGINT;         (* L„nge dieses Bereiches              *)
  57.                REF substr : ARRAY OF CHAR;   (* gesuchter String                    *)
  58.                    len    : INTEGER;        (* L„nge dieses Strings                *)
  59.                    gross  : BOOLEAN;         (* gross-klein unterscheiden?          *)
  60.                REF table  : tableType): LONGINT; (* Mit InitTable angelegte Tabelle *)
  61. (* Macht genau das gleiche wie Pos, sucht nur Rckw„rts im Buffer *)
  62.  
  63. END BoyerMoore.
  64.